SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Consensus (computer science)</title>

</head>

Consensus (computer science)

</h1>

</header>

A fundamental problem in <a href="Distributed_computing" title="Distributed computing">distributed computing</a> and <a href="Multi-agent_system" title="Multi-agent system">multi-agent systems</a> is to achieve overall system reliability in the presence of a number of faulty processes. This often requires coordinating processes to reach consensus, or agree on some data value that is needed during computation. Example applications of consensus include agreeing on what transactions to commit to a database in which order, <a href="State_machine_replication" title="State machine replication">state machine replication</a>, and <a href="Atomic_broadcast" title="Atomic broadcast">atomic broadcasts</a>. Real-world applications often requiring consensus include <a href="Cloud_computing" title="Cloud computing">cloud computing</a>, <a href="Clock_synchronization" title="Clock synchronization">clock synchronization</a>, <a href="PageRank" title="PageRank">PageRank</a>, opinion formation, <a href="Smart_grid" title="Smart grid">smart power grids</a>, <a href="State_estimation" class="mw-redirect" title="State estimation">state estimation</a>, <a href="Unmanned_aerial_vehicle" title="Unmanned aerial vehicle">control of UAVs</a> (and multiple robots/agents in general), <a href="Load_balancing_(computing)" title="Load balancing (computing)">load balancing</a>, <a href="Blockchain" title="Blockchain">blockchain</a>, and others.

<div class="mw-heading mw-heading2"><h2 id="Problem_description">Problem description</h2></div>

The consensus problem requires agreement among a number of processes (or agents) on a single data value. Some of the processes (agents) may fail or be unreliable in other ways, so consensus protocols must be <a href="Fault_tolerant" class="mw-redirect" title="Fault tolerant">fault-tolerant</a> or resilient. The processes must put forth their candidate values, communicate with one another, and agree on a single consensus value.

The consensus problem is a fundamental problem in controlling multi-agent systems. One approach to generating consensus is for all processes (agents) to agree on a majority value. In this context, a majority requires at least one more than half of the available votes (where each process is given a vote). However, one or more faulty processes may skew the resultant outcome such that consensus may not be reached or may be reached incorrectly.

Protocols that solve consensus problems are designed to deal with a limited number of faulty <a href="Process_(computing)" title="Process (computing)">processes</a>. These protocols must satisfy several requirements to be useful. For instance, a trivial protocol could have all processes output binary value 1. This is not useful; thus, the requirement is modified such that the production must depend on the input. That is, the output value of a consensus protocol must be the input value of some process. Another requirement is that a process may decide upon an output value only once, and this decision is irrevocable. A method is correct in an execution if it does not experience a failure. A consensus protocol tolerating halting failures must satisfy the following properties.<a href="#cite_note-coulouris-1">[1]</a>

<dl><dt>Termination</dt>

<dd>Eventually, every correct process decides some value.</dd>

<dt>Integrity</dt>

<dd>If all the correct processes proposed the same value <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy">, then any correct process must decide <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy">.</dd>

<dt>Agreement</dt>

<dd>Every correct process must agree on the same value.</dd></dl>

Variations on the definition of integrity may be appropriate, according to the application. For example, a weaker type of integrity would be for the decision value to equal a value that some correct process proposed – not necessarily all of them.<a href="#cite_note-coulouris-1">[1]</a> There is also a condition known as validity in the literature which refers to the property that a message sent by a process must be delivered.<a href="#cite_note-coulouris-1">[1]</a>

A protocol that can correctly guarantee consensus amongst n processes of which at most t fail is said to be t-resilient.

In evaluating the performance of consensus protocols two factors of interest are running time and message complexity. Running time is given in <a href="Big_O_notation" title="Big O notation">Big O notation</a> in the number of rounds of message exchange as a function of some input parameters (typically the number of processes and/or the size of the input domain). Message complexity refers to the amount of message traffic that is generated by the protocol. Other factors may include memory usage and the size of messages.

<div class="mw-heading mw-heading2"><h2 id="Models_of_computation">Models of computation</h2></div>

Varying models of computation may define a "consensus problem". Some models may deal with fully connected graphs, while others may deal with rings and trees. In some models message authentication is allowed, whereas in others processes are completely anonymous. Shared memory models in which processes communicate by accessing objects in shared memory are also an important area of research.

<div class="mw-heading mw-heading3"><h3 id="Communication_channels_with_direct_or_transferable_authentication">Communication channels with direct or transferable authentication</h3></div>

In most models of communication protocol participants communicate through authenticated channels. This means that messages are not anonymous, and receivers know the source of every message they receive.

Some models assume a stronger, transferable form of authentication, where each message is signed by the sender, so that a receiver knows not just the immediate source of every message, but the participant that initially created the message.

This stronger type of authentication is achieved by digital signatures, and when this stronger form of authentication is available, protocols can tolerate a larger number of faults.<a href="#cite_note-dolev_strong-2">[2]</a>

The two different authentication models are often called oral communication and written communication models. In an oral communication model, the immediate source of information is known, whereas in stronger, written communication models, every step along the receiver learns not just the immediate source of the message, but the communication history of the message.<a href="#cite_note-GLR95-3">[3]</a>

<div class="mw-heading mw-heading3"><h3 id="Inputs_and_outputs_of_consensus">Inputs and outputs of consensus</h3></div>

In the most traditional single-value consensus protocols such as <a href="Paxos_(computer_science)" title="Paxos (computer science)">Paxos</a>, cooperating nodes agree on a single value such as an integer, which may be of variable size so as to encode useful <a href="Metadata" title="Metadata">metadata</a> such as a transaction committed to a database.

A special case of the single-value consensus problem, called binary consensus, restricts the input, and hence the output domain, to a single binary digit {0,1}. While not highly useful by themselves, binary consensus protocols are often useful as building blocks in more general consensus protocols, especially for asynchronous consensus.

In multi-valued consensus protocols such as <a href="Paxos_(computer_science)#Multi-Paxos" title="Paxos (computer science)">Multi-Paxos</a> and <a href="Raft_(algorithm)" title="Raft (algorithm)">Raft</a>, the goal is to agree on not just a single value but a series of values over time, forming a progressively-growing history. While multi-valued consensus may be achieved naively by running multiple iterations of a single-valued consensus protocol in succession, many optimizations and other considerations such as reconfiguration support can make multi-valued consensus protocols more efficient in practice.

<div class="mw-heading mw-heading3"><h3 id="Crash_and_Byzantine_failures">Crash and Byzantine failures</h3></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">See also: <a href="Byzantine_failure" class="mw-redirect" title="Byzantine failure">Byzantine failure</a></div>

There are two types of failures a process may undergo, a crash failure or a <a href="Byzantine_failure" class="mw-redirect" title="Byzantine failure">Byzantine failure</a>. A crash failure occurs when a process abruptly stops and does not resume. Byzantine failures are failures in which absolutely no conditions are imposed. For example, they may occur as a result of the malicious actions of an adversary. A process that experiences a Byzantine failure may send contradictory or conflicting data to other processes, or it may sleep and then resume activity after a lengthy delay. Of the two types of failures, Byzantine failures are far more disruptive.

Thus, a consensus protocol tolerating Byzantine failures must be resilient to every possible error that can occur.

A stronger version of consensus tolerating Byzantine failures is given by strengthening the Integrity constraint:

<dl><dt>Integrity</dt>

<dd>If a correct process decides <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy">, then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"> must have been proposed by some correct process.</dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Asynchronous_and_synchronous_systems">Asynchronous and synchronous systems</h3></div>

The consensus problem may be considered in the case of asynchronous or synchronous systems. While real world communications are often inherently asynchronous, it is more practical and often easier to model synchronous systems,<a href="#cite_note-aguilera_stumbling-4">[4]</a> given that asynchronous systems naturally involve more issues than synchronous ones.

In synchronous systems, it is assumed that all communications proceed in rounds. In one round, a process may send all the messages it requires, while receiving all messages from other processes. In this manner, no message from one round may influence any messages sent within the same round.

<div class="mw-heading mw-heading4"><h4 id="The_FLP_impossibility_result_for_asynchronous_deterministic_consensus">The FLP impossibility result for asynchronous deterministic consensus</h4></div>

In a fully asynchronous message-passing distributed system, in which at least one process may have a crash failure, it has been proven in the famous 1985 FLP impossibility result by Fischer, Lynch and Paterson that a <a href="Deterministic_algorithm" title="Deterministic algorithm">deterministic algorithm</a> for achieving consensus is impossible.<a href="#cite_note-fischer_impossibility-5">[5]</a> This impossibility result derives from worst-case scheduling scenarios, which are unlikely to occur in practice except in adversarial situations such as an intelligent <a href="Denial-of-service_attack" title="Denial-of-service attack">denial-of-service attacker</a> in the network. In most normal situations, process scheduling has a degree of natural randomness.<a href="#cite_note-aguilera_stumbling-4">[4]</a>

In an asynchronous model, some forms of failures can be handled by a synchronous consensus protocol. For instance, the loss of a communication link may be modeled as a process which has suffered a Byzantine failure.

<a href="Randomized_algorithm" title="Randomized algorithm">Randomized</a> consensus algorithms can circumvent the FLP impossibility result by achieving both safety and liveness with overwhelming probability, even under worst-case scheduling scenarios such as an intelligent denial-of-service attacker in the network.<a href="#cite_note-6">[6]</a>

<div class="mw-heading mw-heading3"><h3 id="Permissioned_versus_permissionless_consensus">Permissioned versus permissionless consensus</h3></div>

Consensus algorithms traditionally assume that the set of participating nodes is fixed and given at the outset: that is, that some prior (manual or automatic) configuration process has permissioned a particular known group of participants who can authenticate each other as members of the group. In the absence of such a well-defined, closed group with authenticated members, a <a href="Sybil_attack" title="Sybil attack">Sybil attack</a> against an open consensus group can defeat even a Byzantine consensus algorithm, simply by creating enough virtual participants to overwhelm the fault tolerance threshold.

A permissionless consensus protocol, in contrast, allows anyone in the network to join dynamically and participate without prior permission, but instead imposes a different form of artificial cost or <a href="Barriers_to_entry" title="Barriers to entry">barrier to entry</a> to mitigate the <a href="Sybil_attack" title="Sybil attack">Sybil attack</a> threat. <a href="Bitcoin" title="Bitcoin">Bitcoin</a> introduced the first permissionless consensus protocol using <a href="Proof_of_work" title="Proof of work">proof of work</a> and a difficulty adjustment function, in which participants compete to solve cryptographic <a href="Cryptographic_hash_function" title="Cryptographic hash function">hash</a> puzzles, and probabilistically earn the right to commit blocks and earn associated rewards in proportion to their invested computational effort. Motivated in part by the high energy cost of this approach, subsequent permissionless consensus protocols have proposed or adopted other alternative participation rules for Sybil attack protection, such as <a href="Proof_of_stake" title="Proof of stake">proof of stake</a>, <a href="Proof_of_space" title="Proof of space">proof of space</a>, and <a href="Proof_of_authority" title="Proof of authority">proof of authority</a>.

<div class="mw-heading mw-heading2"><h2 id="Equivalency_of_agreement_problems">Equivalency of agreement problems</h2></div>

Three agreement problems of interest are as follows.

<div class="mw-heading mw-heading3"><h3 id="Terminating_Reliable_Broadcast">Terminating Reliable Broadcast</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Terminating_Reliable_Broadcast" title="Terminating Reliable Broadcast">Terminating Reliable Broadcast</a></div>

A collection of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> processes, numbered from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>

</semantics>

</math><img src="./2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n-1,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n-1,}</annotation>

</semantics>

</math><img src="./8ea7e6006d94fc413924203051db13c3f6253a53.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.044ex; height:2.509ex;" alt="{\displaystyle n-1,}" loading="lazy"> communicate by sending messages to one another. Process <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>

</semantics>

</math><img src="./2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy"> must transmit a value <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"> to all processes such that:

<ol><li>if process <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>

</semantics>

</math><img src="./2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy"> is correct, then every correct process receives <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"></li>

<li>for any two correct processes, each process receives the same value.</li></ol>

It is also known as The General's Problem.

<div class="mw-heading mw-heading3"><h3 id="Consensus">Consensus</h3></div>

Formal requirements for a consensus protocol may include:

<ul><li>Agreement: All correct processes must agree on the same value.</li>

<li>Weak validity: For each correct process, its output must be the input of some correct process.</li>

<li>Strong validity: If all correct processes receive the same input value, then they must all output that value.</li>

<li>Termination: All processes must eventually decide on an output value</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Weak_Interactive_Consistency">Weak Interactive Consistency</h3></div>

For n processes in a partially synchronous system (the system alternates between good and bad periods of synchrony), each process chooses a private value. The processes communicate with each other by rounds to determine a public value and generate a

consensus vector with the following requirements:<a href="#cite_note-7">[7]</a>

<ol><li>if a correct process sends <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy">, then all correct processes receive either <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"> or nothing (integrity property)</li>

<li>all messages sent in a round by a correct process are received in the same round by all correct processes (consistency property).</li></ol>

It can be shown that variations of these problems are equivalent in that the solution for a problem in one type of model may be the solution for another problem in another type of model. For example, a solution to the Weak Byzantine General problem in a synchronous authenticated message passing model leads to a solution for Weak Interactive Consistency.<a href="#cite_note-lamport_WBGP-8">[8]</a> An interactive consistency algorithm can solve the consensus problem by having each process choose the majority value in its consensus vector as its consensus value.<a href="#cite_note-9">[9]</a>

<div class="mw-heading mw-heading2"><h2 id="Solvability_results_for_some_agreement_problems">Solvability results for some agreement problems</h2></div>

There is a t-resilient anonymous synchronous protocol which solves the <a href="Byzantine_Generals_problem" class="mw-redirect" title="Byzantine Generals problem">Byzantine Generals problem</a>,<a href="#cite_note-PSL82-10">[10]</a><a href="#cite_note-11">[11]</a> if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tfrac {t}{n}}<{\tfrac {1}{3}}}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tfrac {t}{n}}<{\tfrac {1}{3}}}</annotation>

</semantics>

</math><img src="./57deb1ece44270ce2368baaf9b88f9f421a0c995.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:6.579ex; height:3.676ex;" alt="{\displaystyle {\tfrac {t}{n}}<{\tfrac {1}{3}}}" loading="lazy"> and the Weak Byzantine Generals case<a href="#cite_note-lamport_WBGP-8">[8]</a> where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"> is the number of failures and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> is the number of processes.

For systems with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> processors, of which <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> are Byzantine, it has been shown that there exists no algorithm that solves the consensus problem for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\leq 3f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\leq 3f}</annotation>

</semantics>

</math><img src="./a5920860a73955c7d35c3d3beef84fa0f020b11a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.934ex; height:2.509ex;" alt="{\displaystyle n\leq 3f}" loading="lazy"> in the oral-messages model.<a href="#cite_note-12">[12]</a> The proof is constructed by first showing the impossibility for the three-node case <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=3}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=3}</annotation>

</semantics>

</math><img src="./1c5a5a42ced00df920fad4ab2d4acdb960a4105b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.656ex; height:2.176ex;" alt="{\displaystyle n=3}" loading="lazy"> and using this result to argue about partitions of processors. In the written-messages model there are protocols that can tolerate <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=f+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=f+1}</annotation>

</semantics>

</math><img src="./2f858fea4ec3e7c7f90e9dead35baef1f86590fc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.775ex; height:2.509ex;" alt="{\displaystyle n=f+1}" loading="lazy">.<a href="#cite_note-dolev_strong-2">[2]</a>

In a fully asynchronous system there is no consensus solution that can tolerate one or more crash failures even when only requiring the non triviality property.<a href="#cite_note-fischer_impossibility-5">[5]</a> This result is sometimes called the FLP impossibility proof named after the authors <a href="Michael_J._Fischer" title="Michael J. Fischer">Michael J. Fischer</a>, <a href="Nancy_Lynch" title="Nancy Lynch">Nancy Lynch</a>, and <a href="Mike_Paterson" title="Mike Paterson">Mike Paterson</a> who were awarded a <a href="Dijkstra_Prize" class="mw-redirect" title="Dijkstra Prize">Dijkstra Prize</a> for this significant work. The FLP result has been mechanically verified to hold even under <a href="Unbounded_nondeterminism#Fairness" title="Unbounded nondeterminism">fairness assumptions</a>.<a href="#cite_note-flp_verification-13">[13]</a> However, FLP does not state that consensus can never be reached: merely that under the model's assumptions, no algorithm can always reach consensus in bounded time. In practice it is highly unlikely to occur.

<div class="mw-heading mw-heading2"><h2 id="Some_consensus_protocols">Some consensus protocols</h2></div>

The <a href="Paxos_(computer_science)" title="Paxos (computer science)">Paxos</a> consensus algorithm by <a href="Leslie_Lamport" title="Leslie Lamport">Leslie Lamport</a>, and variants of it such as <a href="Raft_(algorithm)" title="Raft (algorithm)">Raft</a>, are used pervasively in widely deployed <a href="Distributed_computing" title="Distributed computing">distributed</a> and <a href="Cloud_computing" title="Cloud computing">cloud computing</a> systems. These algorithms are typically synchronous, dependent on an elected leader to make progress, and tolerate only crashes and not Byzantine failures.

An example of a polynomial time binary consensus protocol that tolerates Byzantine failures is the Phase King algorithm by Garay and Berman.<a href="#cite_note-14">[14]</a> The algorithm solves consensus in a synchronous message passing model with n processes and up to f failures, provided n > 4f.

In the phase king algorithm, there are f + 1 phases, with 2 rounds per phase.

Each process keeps track of its preferred output (initially equal to the process's own input value). In the first round of each phase each process broadcasts its own preferred value to all other processes. It then receives the values from all processes and determines which value is the majority value and its count. In the second round of the phase, the process whose id matches the current phase number is designated the king of the phase. The king broadcasts the majority value it observed in the first round and serves as a tie breaker. Each process then updates its preferred value as follows. If the count of the majority value the process observed in the first round is greater than n/2 + f, the process changes its preference to that majority value; otherwise it uses the phase king's value. At the end of f + 1 phases the processes output their preferred values.

Google has implemented a <a href="Distributed_lock_manager" title="Distributed lock manager">distributed lock service</a> library called <a href="Distributed_lock_manager#Google's_Chubby_lock_service" title="Distributed lock manager">Chubby</a>.<a href="#cite_note-15">[15]</a> Chubby maintains lock information in small files which are stored in a replicated database to achieve high availability in the face of failures. The database is implemented on top of a fault-tolerant log layer which is based on the <a href="Paxos_algorithm" class="mw-redirect" title="Paxos algorithm">Paxos consensus algorithm</a>. In this scheme, Chubby clients communicate with the Paxos master in order to access/update the replicated log; i.e., read/write to the files.<a href="#cite_note-16">[16]</a>

Many peer-to-peer online <a href="Real-time_strategy" title="Real-time strategy">real-time strategy</a> games use a modified <a href="Lockstep_protocol" title="Lockstep protocol">lockstep protocol</a> as a consensus protocol in order to manage game state between players in a game. Each game action results in a game state delta broadcast to all other players in the game along with a hash of the total game state. Each player validates the change by applying the delta to their own game state and comparing the game state hashes. If the hashes do not agree then a vote is cast, and those players whose game state is in the minority are disconnected and removed from the game (known as a desync.)

Another well-known approach is called MSR-type algorithms which have been used widely in fields from computer science to control theory.<a href="#cite_note-17">[17]</a><a href="#cite_note-18">[18]</a><a href="#cite_note-19">[19]</a>

<th>Source</th>

<th>Synchrony</th>

<th>Authentication</th>

<th>Threshold</th>

<th>Rounds</th>

<th>Notes

</th></tr>

<tr>

<td>Pease-Shostak-Lamport <a href="#cite_note-PSL82-10">[10]</a></td>

<td>Synchronous</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n>3f}</annotation>

</semantics>

</math><img src="./a6618f7c6b42488a6f0436efc6a7fc29ebff7f70.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.934ex; height:2.509ex;" alt="{\displaystyle n>3f}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f+1}</annotation>

</semantics>

</math><img src="./aee21b648efc2c741b011553fb081d3c0f02a3a3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.281ex; height:2.509ex;" alt="{\displaystyle f+1}" loading="lazy"></td>

<td>total communication <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{f})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{f})}</annotation>

</semantics>

</math><img src="./c16cd7a6b490f7385d318f6250eece0984554106.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.114ex; height:3.176ex;" alt="{\displaystyle O(n^{f})}" loading="lazy">

</td></tr>

<tr>

<td>Pease-Shostak-Lamport <a href="#cite_note-PSL82-10">[10]</a></td>

<td>Synchronous</td>

<td>Written</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n>f+1}</annotation>

</semantics>

</math><img src="./84709ec48d055580110da72f9134be4d55e9b516.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.775ex; height:2.509ex;" alt="{\displaystyle n>f+1}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f+1}</annotation>

</semantics>

</math><img src="./aee21b648efc2c741b011553fb081d3c0f02a3a3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.281ex; height:2.509ex;" alt="{\displaystyle f+1}" loading="lazy"></td>

<td>total communication <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{f})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{f})}</annotation>

</semantics>

</math><img src="./c16cd7a6b490f7385d318f6250eece0984554106.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.114ex; height:3.176ex;" alt="{\displaystyle O(n^{f})}" loading="lazy">

</td></tr>

<tr>

<td>Asynchronous</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n>5f}</annotation>

</semantics>

</math><img src="./b0fa2c977c68df624391bc377be6139a01dacc49.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.934ex; height:2.509ex;" alt="{\displaystyle n>5f}" loading="lazy"></td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(2^{n})}</annotation>

</semantics>

</math><img src="./d4b1a4ff0bc4f81ebf79f28260c6fb54ee08ff8d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.964ex; height:2.843ex;" alt="{\displaystyle O(2^{n})}" loading="lazy"> (expected)</td>

<td>expected <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(1)}</annotation>

</semantics>

</math><img src="./e66384bc40452c5452f33563fe0e27e803b0cc21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\displaystyle O(1)}" loading="lazy"> rounds when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f<{\sqrt {n}}}">

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f<{\sqrt {n}}}</annotation>

</semantics>

</math><img src="./c9169516623e50f27ac8736b9357fe56b3ba2954.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:7.708ex; height:3.009ex;" alt="{\displaystyle f<{\sqrt {n}}}" loading="lazy">

</td></tr>

<tr>

<td>Dolev et al.<a href="#cite_note-DFFLS82-21">[21]</a></td>

<td>Synchronous</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n>3f}</annotation>

</semantics>

</math><img src="./a6618f7c6b42488a6f0436efc6a7fc29ebff7f70.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.934ex; height:2.509ex;" alt="{\displaystyle n>3f}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2f+3}</annotation>

</semantics>

</math><img src="./3c23dc3399c2c81e6c69dfe72629c6c3e2b515cb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.444ex; height:2.509ex;" alt="{\displaystyle 2f+3}" loading="lazy"></td>

<td>total communication <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(f^{3}\log f)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(f^{3}\log f)}</annotation>

</semantics>

</math><img src="./1514c727b09e8faf3678ce5117ff48b2936671dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.982ex; height:3.176ex;" alt="{\displaystyle O(f^{3}\log f)}" loading="lazy">

</td></tr>

<tr>

<td>Dolev-Strong <a href="#cite_note-dolev_strong-2">[2]</a></td>

<td>Synchronous</td>

<td>Written</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n>f+1}</annotation>

</semantics>

</math><img src="./84709ec48d055580110da72f9134be4d55e9b516.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.775ex; height:2.509ex;" alt="{\displaystyle n>f+1}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f+1}</annotation>

</semantics>

</math><img src="./aee21b648efc2c741b011553fb081d3c0f02a3a3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.281ex; height:2.509ex;" alt="{\displaystyle f+1}" loading="lazy"></td>

<td>total communication <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{2})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{2})}</annotation>

</semantics>

</math><img src="./6cd9594a16cb898b8f2a2dff9227a385ec183392.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:3.176ex;" alt="{\displaystyle O(n^{2})}" loading="lazy">

</td></tr>

<tr>

<td>Dolev-Strong <a href="#cite_note-dolev_strong-2">[2]</a></td>

<td>Synchronous</td>

<td>Written</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n>f+1}</annotation>

</semantics>

</math><img src="./84709ec48d055580110da72f9134be4d55e9b516.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.775ex; height:2.509ex;" alt="{\displaystyle n>f+1}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f+2}</annotation>

</semantics>

</math><img src="./8892ba91a4105be98c0180380c167947884c1447.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.281ex; height:2.509ex;" alt="{\displaystyle f+2}" loading="lazy"></td>

<td>total communication <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(nf)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(nf)}</annotation>

</semantics>

</math><img src="./d3f2fca86f440762266e690bc831ac35ea69c500.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.256ex; height:2.843ex;" alt="{\displaystyle O(nf)}" loading="lazy">

</td></tr>

<tr>

<td>Feldman-Micali <a href="#cite_note-FM97-22">[22]</a></td>

<td>Synchronous</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n>3f}</annotation>

</semantics>

</math><img src="./a6618f7c6b42488a6f0436efc6a7fc29ebff7f70.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.934ex; height:2.509ex;" alt="{\displaystyle n>3f}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(1)}</annotation>

</semantics>

</math><img src="./e66384bc40452c5452f33563fe0e27e803b0cc21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\displaystyle O(1)}" loading="lazy"> (expected)</td>

<td>

</td></tr>

<tr>

<td>Synchronous</td>

<td>Written</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n>2f}</annotation>

</semantics>

</math><img src="./05cc4d82ca126d44ab32e0f4ca4e2ca26097bee8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.934ex; height:2.509ex;" alt="{\displaystyle n>2f}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(1)}</annotation>

</semantics>

</math><img src="./e66384bc40452c5452f33563fe0e27e803b0cc21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\displaystyle O(1)}" loading="lazy"> (expected)</td>

<td>Requires <a href="Public_Key_Infrastructure" class="mw-redirect" title="Public Key Infrastructure">Public Key Infrastructure</a> (PKI)

</td></tr>

<tr>

<td>Asynchronous (safety) Synchronous (liveness)</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n>3f}</annotation>

</semantics>

</math><img src="./a6618f7c6b42488a6f0436efc6a7fc29ebff7f70.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.934ex; height:2.509ex;" alt="{\displaystyle n>3f}" loading="lazy"></td>

<td>

</td></tr>

<tr>

<td>HoneyBadger <a href="#cite_note-HoneyBadger-25">[25]</a></td>

<td>Asynchronous</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n>3f}</annotation>

</semantics>

</math><img src="./a6618f7c6b42488a6f0436efc6a7fc29ebff7f70.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.934ex; height:2.509ex;" alt="{\displaystyle n>3f}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation>

</semantics>

</math><img src="./aae0f22048ba6b7c05dbae17b056bfa16e21807d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle O(\log n)}" loading="lazy"> (expected)</td>

<td>per tx communication <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation>

</semantics>

</math><img src="./34109fe397fdcff370079185bfdb65826cb5565a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}" loading="lazy"> - requires public-key encryption

</td></tr>

<tr>

<td>Abraham et al.<a href="#cite_note-ADDNR17-26">[26]</a></td>

<td>Synchronous</td>

<td>Written</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n>2f}</annotation>

</semantics>

</math><img src="./05cc4d82ca126d44ab32e0f4ca4e2ca26097bee8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.934ex; height:2.509ex;" alt="{\displaystyle n>2f}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 8}</annotation>

</semantics>

</math><img src="./1aaa997e6ad67716cfaa9a02c4df860bf60a95b5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 8}" loading="lazy"></td>

<td>

</td></tr>

<tr>

<td>Byzantine Agreement Made Trivial <a href="#cite_note-M18-27">[27]</a><a href="#cite_note-28">[28]</a></td>

<td>Synchronous</td>

<td>Signatures</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n>3f}</annotation>

</semantics>

</math><img src="./a6618f7c6b42488a6f0436efc6a7fc29ebff7f70.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.934ex; height:2.509ex;" alt="{\displaystyle n>3f}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 9}</annotation>

</semantics>

</math><img src="./32d3d1e1f9dfe0254c628379e69a69711fe4eabd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 9}" loading="lazy"> (expected)</td>

<td>Requires digital signatures

</td></tr>

</tbody></table>

<div class="mw-heading mw-heading3"><h3 id="Permissionless_consensus_protocols">Permissionless consensus protocols</h3></div>

<a href="Bitcoin" title="Bitcoin">Bitcoin</a> uses <a href="Proof_of_work" title="Proof of work">proof of work</a>, a difficulty adjustment function and a reorganization function to achieve permissionless consensus in its open <a href="Peer-to-peer" title="Peer-to-peer">peer-to-peer</a> network. To extend bitcoin's <a href="Blockchain" title="Blockchain">blockchain</a> or <a href="Distributed_ledger" title="Distributed ledger">distributed ledger</a>, miners attempt to solve a cryptographic puzzle, where probability of finding a solution is proportional to the computational effort expended in hashes per second. The node that first solves such a puzzle has their proposed version of the next block of transactions added to the ledger and eventually accepted by all other nodes. As any node in the network can attempt to solve the proof-of-work problem, a Sybil attack is infeasible in principle unless the attacker has over 50% of the computational resources of the network.

Other cryptocurrencies (e.g. <a href="Ethereum" title="Ethereum">Ethereum</a>, NEO, STRATIS, ...) use <a href="Proof_of_stake" title="Proof of stake">proof of stake</a>, in which nodes compete to append blocks and earn associated rewards in proportion to stake, or existing cryptocurrency allocated and locked or staked for some time period. One advantage of a 'proof of stake' over a 'proof of work' system, is the high energy consumption demanded by the latter. As an example, bitcoin mining (2018) is estimated to consume non-renewable energy sources at an amount similar to the entire nations of Czech Republic or Jordan, while the total energy consumption of Ethereum, the largest proof of stake network, is just under that of 205 average US households.<a href="#cite_note-29">[29]</a><a href="#cite_note-30">[30]</a><a href="#cite_note-31">[31]</a>

Some cryptocurrencies, such as Ripple, use a system of validating nodes to validate the ledger.

This system used by Ripple, called Ripple Protocol Consensus Algorithm (RPCA), works in rounds:

<dl><dd>Step 1: every server compiles a list of valid candidate transactions;</dd>

<dd>Step 2: each server amalgamates all candidates coming from its Unique Nodes List (UNL) and votes on their veracity;</dd>

<dd>Step 3: transactions passing the minimum threshold are passed to the next round;</dd>

<dd>Step 4: the final round requires 80% agreement.<a href="#cite_note-32">[32]</a></dd></dl>

Other participation rules used in permissionless consensus protocols to impose <a href="Barriers_to_entry" title="Barriers to entry">barriers to entry</a> and resist sybil attacks include <a href="Proof_of_authority" title="Proof of authority">proof of authority</a>, <a href="Proof_of_space" title="Proof of space">proof of space</a>, proof of burn, or proof of elapsed time.

Contrasting with the above permissionless participation rules, all of which reward participants in proportion to amount of investment in some action or resource, <a href="Proof_of_personhood" title="Proof of personhood">proof of personhood</a> protocols aim to give each real human participant exactly one unit of voting power in permissionless consensus, regardless of economic investment.<a href="#cite_note-33">[33]</a><a href="#cite_note-34">[34]</a> Proposed approaches to achieving one-per-person distribution of consensus power for proof of personhood include physical pseudonym parties,<a href="#cite_note-35">[35]</a> social networks,<a href="#cite_note-36">[36]</a> pseudonymized government-issued identities,<a href="#cite_note-37">[37]</a> and biometrics.<a href="#cite_note-38">[38]</a>

<div class="mw-heading mw-heading2"><h2 id="Consensus_number">Consensus number</h2></div>

To solve the consensus problem in a shared-memory system, concurrent objects must be introduced. A concurrent object, or shared object, is a data structure which helps concurrent processes communicate to reach an agreement. Traditional implementations using <a href="Critical_section" title="Critical section">critical sections</a> face the risk of crashing if some process dies inside the critical section or sleeps for an intolerably long time. Researchers defined <a href="Non-blocking_algorithm#Wait-freedom" title="Non-blocking algorithm">wait-freedom</a> as the guarantee that the algorithm completes in a finite number of steps.

The consensus number of a concurrent object is defined to be the maximum number of processes in the system which can reach consensus by the given object in a wait-free implementation.<a href="#cite_note-hierarchy-39">[39]</a> Objects with a consensus number of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> can implement any object with a consensus number of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> or lower, but cannot implement any objects with a higher consensus number. The consensus numbers form what is called <a href="Maurice_Herlihy" title="Maurice Herlihy">Herlihy</a>'s hierarchy of synchronization objects.<a href="#cite_note-40">[40]</a>

<th>Consensus number</th>

<th>Objects

</th></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math><img src="./92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy"></td>

<td><a href="Atomic_semantics" title="Atomic semantics">atomic</a> <a href="Shared_register" title="Shared register">read/write registers</a>, <a href="Lock_(computer_science)" title="Lock (computer science)">mutex</a>

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2}</annotation>

</semantics>

</math><img src="./901fc910c19990d0dbaaefe4726ceb1a4e217a0f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 2}" loading="lazy"></td>

<td><a href="Test-and-set" title="Test-and-set">test-and-set</a>, <a href="Swap_(computer_programming)" title="Swap (computer programming)">swap</a>, <a href="Fetch-and-add" title="Fetch-and-add">fetch-and-add</a>, wait-free <a href="Queue_(abstract_data_type)" title="Queue (abstract data type)">queue</a> or <a href="Stack_(abstract_data_type)" title="Stack (abstract data type)">stack</a>

</td></tr>

<tr>

<td>...

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2n-2}</annotation>

</semantics>

</math><img src="./a8593ff30008d016680ae67c34865b96087b62fa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.56ex; height:2.343ex;" alt="{\displaystyle 2n-2}" loading="lazy"></td>

<td>n-register assignment

</td></tr>

<tr>

<td>...

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \infty }</annotation>

</semantics>

</math><img src="./c26c105004f30c27aa7c2a9c601550a4183b1f21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.324ex; height:1.676ex;" alt="{\displaystyle \infty }" loading="lazy"></td>

<td><a href="Compare-and-swap" title="Compare-and-swap">compare-and-swap</a>, <a href="Load-link/store-conditional" title="Load-link/store-conditional">load-link/store-conditional</a>,<a href="#cite_note-41">[41]</a> memory-to-memory move and swap, queue with peek operation, fetch&cons, sticky byte

</td></tr></tbody></table>

According to the hierarchy, read/write registers cannot solve consensus even in a 2-process system. Data structures like stacks and queues can only solve consensus between two processes. However, some concurrent objects are universal (notated in the table with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \infty }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \infty }</annotation>

</semantics>

</math><img src="./c26c105004f30c27aa7c2a9c601550a4183b1f21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.324ex; height:1.676ex;" alt="{\displaystyle \infty }" loading="lazy">), which means they can solve consensus among any number of processes and they can simulate any other objects through an operation sequence.<a href="#cite_note-hierarchy-39">[39]</a>

<ul><li><a href="Uniform_consensus" title="Uniform consensus">Uniform consensus</a></li>

<li><a href="Quantum_Byzantine_agreement" title="Quantum Byzantine agreement">Quantum Byzantine agreement</a></li>

<li><a href="Byzantine_fault" title="Byzantine fault">Byzantine fault</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width" style="column-width: 30em;">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFGeorge_CoulourisJean_DollimoreTim_Kindberg2001" class="citation cs2">George Coulouris; Jean Dollimore; Tim Kindberg (2001), Distributed Systems: Concepts and Design (3rd ed.), Addison-Wesley, p. 452, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0201-61918-8</bdi></cite>

</li>

<li id="cite_note-dolev_strong-2">^ <a href="#cite_ref-dolev_strong_2-0">a</a> <a href="#cite_ref-dolev_strong_2-1">b</a> <a href="#cite_ref-dolev_strong_2-2">c</a> <a href="#cite_ref-dolev_strong_2-3">d</a> <cite id="CITEREFDolevStrong1983" class="citation journal cs1">Dolev, D.; Strong, H.R. (1983). "Authenticated algorithms for Byzantine agreement". SIAM Journal on Computing. 12 (4): 656–666. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0212045">10.1137/0212045</a>.</cite>

</li>

<li id="cite_note-GLR95-3"><a href="#cite_ref-GLR95_3-0">^</a> <cite id="CITEREFGongLincolnRushby1995" class="citation journal cs1">Gong, Li; Lincoln, Patrick; Rushby, John (1995). <a rel="nofollow" class="external text" href="http://www.csl.sri.com/papers/dcca95/">"Byzantine Agreement with authentication"</a>. Dependable Computing for Critical Applications. 10. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20200105080410/http://www.csl.sri.com/papers/dcca95/">Archived</a> from the original on 2020-01-05. Retrieved 2019-05-28.</cite>

</li>

<li id="cite_note-aguilera_stumbling-4">^ <a href="#cite_ref-aguilera_stumbling_4-0">a</a> <a href="#cite_ref-aguilera_stumbling_4-1">b</a> <cite id="CITEREFAguilera2010" class="citation book cs1">Aguilera, M. K. (2010). "Stumbling over Consensus Research: Misunderstandings and Issues". Replication. Lecture Notes in Computer Science. Vol. 5959. pp. 59–72. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-642-11294-2_4">10.1007/978-3-642-11294-2_4</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-642-11293-5</bdi>.</cite>

</li>

<li id="cite_note-fischer_impossibility-5">^ <a href="#cite_ref-fischer_impossibility_5-0">a</a> <a href="#cite_ref-fischer_impossibility_5-1">b</a> <cite id="CITEREFFischerLynchPaterson1985" class="citation journal cs1"><a href="Michael_J._Fischer" title="Michael J. Fischer">Fischer, M. J.</a>; <a href="Nancy_Lynch" title="Nancy Lynch">Lynch, N. A.</a>; <a href="Michael_S._Paterson" class="mw-redirect" title="Michael S. Paterson">Paterson, M. S.</a> (1985). <a rel="nofollow" class="external text" href="https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf">"Impossibility of distributed consensus with one faulty process"</a> (PDF). <a href="Journal_of_the_ACM" title="Journal of the ACM">Journal of the ACM</a>. 32 (2): 374–382. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F3149.214121">10.1145/3149.214121</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:207660233">207660233</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20230130002301/https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf">Archived</a> (PDF) from the original on 2023-01-30. Retrieved 2017-11-13.</cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFAspnes1993" class="citation journal cs1">Aspnes, James (May 1993). <a rel="nofollow" class="external text" href="https://www.sciencedirect.com/science/article/abs/pii/S0196677483710229">"Time- and Space-Efficient Randomized Consensus"</a>. Journal of Algorithms. 14 (3): 414–431. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjagm.1993.1022">10.1006/jagm.1993.1022</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20230216083640/https://www.sciencedirect.com/science/article/abs/pii/S0196677483710229">Archived</a> from the original on 2023-02-16. Retrieved 2020-10-28.</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFMilosevicMartin_HutleAndre_Schiper2009" class="citation book cs1">Milosevic, Zarko; Martin Hutle; Andre Schiper (2009). <a rel="nofollow" class="external text" href="https://archive.org/details/principlesofdist0000opod/page/300">"Unifying Byzantine Consensus Algorithms with Weak Interactive Consistency"</a>. Principles of Distributed Systems. Lecture Notes in Computer Science. Vol. 5293. pp. <a rel="nofollow" class="external text" href="https://archive.org/details/principlesofdist0000opod/page/300">300–314</a>. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.180.4229">10.1.1.180.4229</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-642-10877-8_24">10.1007/978-3-642-10877-8_24</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-642-10876-1</bdi>.</cite> <code class="cs1-code">{{cite book}}</code>: <code class="cs1-code">|journal=</code> ignored (help)

</li>

<li id="cite_note-lamport_WBGP-8">^ <a href="#cite_ref-lamport_WBGP_8-0">a</a> <a href="#cite_ref-lamport_WBGP_8-1">b</a> <cite id="CITEREFLamport1983" class="citation journal cs1">Lamport, L. (1983). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F2402.322398">"The Weak Byzantine Generals Problem"</a>. Journal of the ACM. 30 (3): 668. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F2402.322398">10.1145/2402.322398</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:1574706">1574706</a>.</cite>

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFFischer" class="citation web cs1">Fischer, Michael J. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20140422231847/http://zoo.cs.yale.edu/classes/cs426/2012/bib/fischer83consensus.pdf">"The Consensus Problem in Unreliable Distributed Systems (A Brief Survey)"</a> (PDF). Archived from <a rel="nofollow" class="external text" href="http://zoo.cs.yale.edu/classes/cs426/2012/bib/fischer83consensus.pdf">the original</a> (PDF) on 22 April 2014. Retrieved 21 April 2014.</cite>

</li>

<li id="cite_note-PSL82-10">^ <a href="#cite_ref-PSL82_10-0">a</a> <a href="#cite_ref-PSL82_10-1">b</a> <a href="#cite_ref-PSL82_10-2">c</a> <cite id="CITEREFLamportShostakPease1982" class="citation journal cs1"><a href="Leslie_Lamport" title="Leslie Lamport">Lamport, L.</a>; Shostak, R.; Pease, M. (1982). <a rel="nofollow" class="external text" href="http://research.microsoft.com/en-us/um/people/lamport/pubs/byz.pdf">"The Byzantine Generals Problem"</a> (PDF). ACM Transactions on Programming Languages and Systems. 4 (3): 382–401. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.64.2312">10.1.1.64.2312</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F357172.357176">10.1145/357172.357176</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:55899582">55899582</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20170207104645/http://research.microsoft.com/en-us/um/people/lamport/pubs/byz.pdf">Archived</a> (PDF) from the original on 2017-02-07. Retrieved 2015-08-29.</cite>

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <cite id="CITEREFLamportMarshall_PeaseRobert_Shostak1980" class="citation journal cs1">Lamport, Leslie; Marshall Pease; Robert Shostak (April 1980). <a rel="nofollow" class="external text" href="http://research.microsoft.com/users/lamport/pubs/reaching.pdf">"Reaching Agreement in the Presence of Faults"</a> (PDF). Journal of the ACM. 27 (2): 228–234. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.68.4044">10.1.1.68.4044</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F322186.322188">10.1145/322186.322188</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:6429068">6429068</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20070128004747/http://research.microsoft.com/users/lamport/pubs/reaching.pdf">Archived</a> (PDF) from the original on 2007-01-28. Retrieved 2007-07-25.</cite>

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFAttiya2004" class="citation book cs1"><a href="Hagit_Attiya" title="Hagit Attiya">Attiya, Hagit</a> (2004). Distributed Computing (2nd ed.). Wiley. pp. 101–103. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-471-45324-6</bdi>.</cite>

</li>

<li id="cite_note-flp_verification-13"><a href="#cite_ref-flp_verification_13-0">^</a> <cite id="CITEREFBispingBrodmannJungnickelRickmann2016" class="citation cs2">Bisping, Benjamin; et al. (2016), "Mechanical Verification of a Constructive Proof for FLP", in Blanchette, Jasmin Christian; Merz, Stephan (eds.), Interactive Theorem Proving, Lecture Notes in Computer Science, vol. 9807, Springer International Publishing, pp. 107–122, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-319-43144-4_7">10.1007/978-3-319-43144-4_7</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-319-43144-4</bdi></cite>

</li>

<li id="cite_note-14"><a href="#cite_ref-14">^</a> <cite id="CITEREFBermanGaray1993" class="citation journal cs1">Berman, Piotr; Garay, Juan A. (1993). "Cloture Votes: n/4-resilient Distributed Consensus in t + 1 rounds". Theory of Computing Systems. 2. 26: 3–19. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01187072">10.1007/BF01187072</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:6102847">6102847</a>.</cite>

</li>

<li id="cite_note-15"><a href="#cite_ref-15">^</a> <cite id="CITEREFBurrows,_M.2006" class="citation conference cs1">Burrows, M. (2006). <a rel="nofollow" class="external text" href="http://research.google.com/archive/chubby-osdi06.pdf">The Chubby lock service for loosely-coupled distributed systems</a> (PDF). Proceedings of the 7th Symposium on Operating Systems Design and Implementation. USENIX Association Berkeley, CA, USA. pp. 335–350. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20091214190102/http://research.google.com/archive/chubby-osdi06.pdf">Archived</a> (PDF) from the original on 2009-12-14. Retrieved 2014-10-28.</cite>

</li>

<cite id="CITEREFTushar,_C.Griesemer,_R.Redstone,_J.2007" class="citation conference cs1">Tushar, C.; Griesemer, R.; Redstone, J. (2007). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20141212001817/http://www.cs.cmu.edu/~pavlo/courses/fall2013/static/papers/p398-chandra.pdf">Paxos Made Live – An Engineering Perspective</a> (PDF). Proceedings of the Twenty-Sixth Annual ACM <a href="Symposium_on_Principles_of_Distributed_Computing" title="Symposium on Principles of Distributed Computing">Symposium on Principles of Distributed Computing</a>. Portland, Oregon, USA: ACM Press New York, NY, USA. pp. 398–407. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1281100.1281103">10.1145/1281100.1281103</a>. Archived from <a rel="nofollow" class="external text" href="http://delivery.acm.org/10.1145/1290000/1281103/p398-chandra.pdf?key1=1281103&key2=4382532021&coll=GUIDE&dl=GUIDE&CFID=15324100&CFTOKEN=95510390">the original</a> (PDF) on 2014-12-12. Retrieved 2008-02-06.</cite>

</li>

<li id="cite_note-17"><a href="#cite_ref-17">^</a> <cite id="CITEREFLeBlanc2013" class="citation journal cs1">LeBlanc, Heath J. (April 2013). "Resilient Asymptotic Consensus in Robust Networks". IEEE Journal on Selected Areas in Communications. 31 (4): 766–781. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.310.5354">10.1.1.310.5354</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FJSAC.2013.130413">10.1109/JSAC.2013.130413</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:11287513">11287513</a>.</cite>

</li>

<li id="cite_note-18"><a href="#cite_ref-18">^</a> <cite id="CITEREFDibaji2015" class="citation journal cs1">Dibaji, S. M. (May 2015). "Consensus of second-order multi-agent systems in the presence of locally bounded faults". Systems & Control Letters. 79: 23–29. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.sysconle.2015.02.005">10.1016/j.sysconle.2015.02.005</a>.</cite>

</li>

<li id="cite_note-19"><a href="#cite_ref-19">^</a> <cite id="CITEREFDibaji2017" class="citation journal cs1">Dibaji, S. M. (July 2017). "Resilient consensus of second-order agent networks: Asynchronous update rules with delays". Automatica. 81: 123–132. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1701.03430">1701.03430</a>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2017arXiv170103430M">2017arXiv170103430M</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.automatica.2017.03.008">10.1016/j.automatica.2017.03.008</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:7467466">7467466</a>.</cite>

</li>

<li id="cite_note-B83-20"><a href="#cite_ref-B83_20-0">^</a> <cite id="CITEREFBen-Or1983" class="citation conference cs1">Ben-Or, Michael (1983). "Another advantage of free choice (extended abstract): Completely asynchronous agreement protocols". Proceedings of the second annual ACM symposium on Principles of distributed computing. pp. 27–30. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F800221.806707">10.1145/800221.806707</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:38215511">38215511</a>.</cite>

</li>

<li id="cite_note-DFFLS82-21"><a href="#cite_ref-DFFLS82_21-0">^</a> <cite id="CITEREFDolevFisherFowlerLynch1982" class="citation journal cs1">Dolev, Danny; Fisher, Michael J.; Fowler, Rob; Lynch, Nancy; Strong, H. Raymond (1982). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0019-9958%2882%2990776-8">"An Efficient Algorithm for Byzantine Agreement without Authentication"</a>. Information and Control. 52 (3): 257–274. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0019-9958%2882%2990776-8">10.1016/S0019-9958(82)90776-8</a>.</cite>

</li>

<li id="cite_note-FM97-22"><a href="#cite_ref-FM97_22-0">^</a> <cite id="CITEREFFeldmanMicali1997" class="citation journal cs1">Feldman, Pesech; Micali, Sylvio (1997). "An optimal probabilistic protocol for synchronous Byzantine agreement". SIAM Journal on Computing. 26 (4): 873–933. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2FS0097539790187084">10.1137/S0097539790187084</a>.</cite>

</li>

<li id="cite_note-KK06-23"><a href="#cite_ref-KK06_23-0">^</a> <cite id="CITEREFKatzKoo2006" class="citation conference cs1">Katz, Jonathan; Koo, Chiu-Yuen (2006). On Expected Constant-Round Protocols for Byzantine Agreement. CRYPTO 2006. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F11818175_27">10.1007/11818175_27</a>.</cite>

</li>

<li id="cite_note-PBFT-24"><a href="#cite_ref-PBFT_24-0">^</a> <cite id="CITEREFCastroLiskov1999" class="citation conference cs1">Castro, Miguel; Liskov, Barbara (1999). <a rel="nofollow" class="external text" href="http://pmg.csail.mit.edu/papers/osdi99.pdf">"Practical Byzantine Fault Tolerance"</a> (PDF). Proceedings of the Third Symposium on Operating Systems Design and Implementation, New Orleans, USA, February 1999. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20180304201549/http://www.pmg.csail.mit.edu/papers/osdi99.pdf">Archived</a> (PDF) from the original on 2018-03-04. Retrieved 2019-05-28.</cite>

</li>

<li id="cite_note-HoneyBadger-25"><a href="#cite_ref-HoneyBadger_25-0">^</a> <cite id="CITEREFMillerXiaCromanShi2016" class="citation conference cs1">Miller, Andrew; Xia, Yu; Croman, Kyle; <a href="Elaine_Shi" title="Elaine Shi">Shi, Elaine</a>; Song, Dawn (October 2016). <a rel="nofollow" class="external text" href="https://eprint.iacr.org/2016/199.pdf">"The honey badger of BFT protocols"</a> (PDF). CCS '16: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. pp. 31–42. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F2976749.2978399">10.1145/2976749.2978399</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20230603183730/https://eprint.iacr.org/2016/199.pdf">Archived</a> (PDF) from the original on 2023-06-03. Retrieved 2023-07-04.</cite>

</li>

<li id="cite_note-ADDNR17-26"><a href="#cite_ref-ADDNR17_26-0">^</a> <cite id="CITEREFAbrahamDevadasDolevNayak2017" class="citation web cs1">Abraham, Ittai; Devadas, Srinivas; Dolev, Danny; Nayak, Kartik; Ren, Ling (September 11, 2017). <a rel="nofollow" class="external text" href="https://eprint.iacr.org/2017/307.pdf">"Efficient Synchronous Byzantine Consensus"</a> (PDF). Cryptology ePrint Archive. Paper 2017/307. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20230704061117/https://eprint.iacr.org/2017/307.pdf">Archived</a> (PDF) from the original on July 4, 2023. Retrieved July 4, 2023.</cite>

</li>

<li id="cite_note-M18-27"><a href="#cite_ref-M18_27-0">^</a> <cite id="CITEREFMicali2018" class="citation web cs1">Micali, Sylvio (March 19, 2018). <a rel="nofollow" class="external text" href="https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Distributed%20Computation/BYZANTYNE%20AGREEMENT%20MADE%20TRIVIAL.pdf">"Byzantine agreement made trivial"</a> (PDF). Cambridge, MA: CSAIL, MIT. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20221207083302/http://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Distributed%20Computation/BYZANTYNE%20AGREEMENT%20MADE%20TRIVIAL.pdf">Archived</a> (PDF) from the original on December 7, 2022. Retrieved May 28, 2019.</cite>

</li>

<li id="cite_note-28"><a href="#cite_ref-28">^</a> <cite id="CITEREFChenMicali2016" class="citation arxiv cs1">Chen, Jing; Micali, Silvio (2016). "ALGORAND". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1607.01341v9">1607.01341v9</a> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/cs.CR">cs.CR</a>].</cite>

</li>

<li id="cite_note-29"><a href="#cite_ref-29">^</a> <cite id="CITEREFIrfan2019" class="citation web cs1">Irfan, Umair (June 18, 2019). <a rel="nofollow" class="external text" href="https://www.vox.com/2019/6/18/18642645/bitcoin-energy-price-renewable-china">"Bitcoin is an energy hog. Where is all that electricity coming from?"</a>. Vox. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20230216083636/https://www.vox.com/2019/6/18/18642645/bitcoin-energy-price-renewable-china">Archived</a> from the original on February 16, 2023. Retrieved August 28, 2019.</cite>

</li>

<li id="cite_note-30"><a href="#cite_ref-30">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://carbon-ratings.com/eth-report-2022">"The Merge - Implications on the Electricity Consumption and Carbon Footprint of the Ethereum Network"</a>. September 7, 2022. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20230905190645/https://carbon-ratings.com/eth-report-2022">Archived</a> from the original on September 5, 2023. Retrieved September 5, 2023.</cite>

</li>

<li id="cite_note-31"><a href="#cite_ref-31">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.statista.com/statistics/383633/worldwide-consumption-of-electricity-by-country/">"Electricity consumption per capita worldwide in 2022, by selected country"</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20230905190644/https://www.statista.com/statistics/383633/worldwide-consumption-of-electricity-by-country/">Archived</a> from the original on 2023-09-05. Retrieved 2023-09-05.</cite>

</li>

<li id="cite_note-32"><a href="#cite_ref-32">^</a> <cite id="CITEREFSchwartzYoungsBritto2014" class="citation web cs1">Schwartz, David; Youngs, Noah; Britto, Arthur (2014). <a rel="nofollow" class="external text" href="https://ripple.com/files/ripple_consensus_whitepaper.pdf">"The Ripple Protocol Consensus Algorithm"</a> (PDF). Ripple Labs (Draft). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20170829061905/https://ripple.com/files/ripple_consensus_whitepaper.pdf">Archived</a> (PDF) from the original on 2017-08-29. Retrieved 2023-07-03.</cite>

</li>

<li id="cite_note-33"><a href="#cite_ref-33">^</a> <cite id="CITEREFMaria_BorgeEleftherios_Kokoris-KogiasPhilipp_JovanovicLinus_Gasser2017" class="citation conference cs1">Maria Borge; Eleftherios Kokoris-Kogias; Philipp Jovanovic; Linus Gasser; Nicolas Gailly; Bryan Ford (29 April 2017). <a rel="nofollow" class="external text" href="https://ieeexplore.ieee.org/document/7966966">Proof-of-Personhood: Redemocratizing Permissionless Cryptocurrencies</a>. <a rel="nofollow" class="external text" href="https://prosecco.gforge.inria.fr/ieee-blockchain2016/">IEEE Security & Privacy on the Blockchain (IEEE S&B)</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FEuroSPW.2017.46">10.1109/EuroSPW.2017.46</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20201112002930/https://ieeexplore.ieee.org/document/7966966">Archived</a> from the original on 12 November 2020. Retrieved 21 December 2020.</cite>

</li>

<li id="cite_note-34"><a href="#cite_ref-34">^</a> <cite id="CITEREFDivya_SiddarthSergey_IvlievSantiago_SiriPaula_Berman2020" class="citation arxiv cs1">Divya Siddarth; Sergey Ivliev; Santiago Siri; Paula Berman (13 Oct 2020). "Who Watches the Watchmen? A Review of Subjective Approaches for Sybil-resistance in Proof of Personhood Protocols". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2008.05300">2008.05300</a> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/cs.CR">cs.CR</a>].</cite>

</li>

<li id="cite_note-35"><a href="#cite_ref-35">^</a> <cite id="CITEREFFordStrauss2008" class="citation conference cs1">Ford, Bryan; Strauss, Jacob (April 2008). <a rel="nofollow" class="external text" href="https://dl.acm.org/doi/10.1145/1435497.1435503">An Offline Foundation for Online Accountable Pseudonyms</a>. <a rel="nofollow" class="external text" href="https://dl.acm.org/doi/proceedings/10.1145/1435497">1st Workshop on Social Network Systems - SocialNets '08</a>. pp. 31–36. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1435497.1435503">10.1145/1435497.1435503</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-60558-124-8</bdi>. Retrieved 2020-10-28.</cite>

</li>

<li id="cite_note-36"><a href="#cite_ref-36">^</a> <cite id="CITEREFGal_ShahafEhud_ShapiroNimrod_Talmon2020" class="citation conference cs1">Gal Shahaf; Ehud Shapiro; Nimrod Talmon (October 2020). <a rel="nofollow" class="external text" href="https://link.springer.com/chapter/10.1007/978-3-030-60975-7_24">Genuine Personal Identifiers and Mutual Sureties for Sybil-Resilient Community Growth</a>. <a rel="nofollow" class="external text" href="https://kdd.isti.cnr.it/socinfo2020/index.html">International Conference on Social Informatics</a>. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1904.09630">1904.09630</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-030-60975-7_24">10.1007/978-3-030-60975-7_24</a>.</cite>

</li>

<li id="cite_note-37"><a href="#cite_ref-37">^</a> <cite id="CITEREFDeepak_MaramHarjasleen_MalvaiFan_ZhangNerla_Jean-Louis2020" class="citation web cs1">Deepak Maram; Harjasleen Malvai; Fan Zhang; Nerla Jean-Louis; Alexander Frolov; Tyler Kell; Tyrone Lobban; Christine Moy; Ari Juels; Andrew Miller (28 Sep 2020). <a rel="nofollow" class="external text" href="https://eprint.iacr.org/2020/934.pdf">"CanDID: Can-Do Decentralized Identity with Legacy Compatibility, Sybil-Resistance, and Accountability"</a> (PDF). <a rel="nofollow" class="external text" href="https://ghostarchive.org/archive/20221009/https://eprint.iacr.org/2020/934.pdf">Archived</a> (PDF) from the original on 9 October 2022. Retrieved 28 October 2020.</cite>

</li>

<li id="cite_note-38"><a href="#cite_ref-38">^</a> <cite id="CITEREFMohammad-Javad_HajialikhaniMohammad-Mahdi_Jahanara2018" class="citation arxiv cs1">Mohammad-Javad Hajialikhani; Mohammad-Mahdi Jahanara (20 June 2018). "UniqueID: Decentralized Proof-of-Unique-Human". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1806.07583">1806.07583</a> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/cs.CR">cs.CR</a>].</cite>

</li>

<li id="cite_note-hierarchy-39">^ <a href="#cite_ref-hierarchy_39-0">a</a> <a href="#cite_ref-hierarchy_39-1">b</a> <cite id="CITEREFHerlihy1991" class="citation journal cs1">Herlihy, Maurice (January 1991). <a rel="nofollow" class="external text" href="http://www.cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf">"Wait-Free Synchronization"</a> (PDF). ACM Transactions on Programming Languages and Systems. 11 (1): 124–149. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F114005.102808">10.1145/114005.102808</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2181446">2181446</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20110605003208/http://www.cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf">Archived</a> (PDF) from the original on 5 June 2011. Retrieved 19 December 2011.</cite>

</li>

<li id="cite_note-40"><a href="#cite_ref-40">^</a> <cite id="CITEREFImbsRaynal2010" class="citation book cs1">Imbs, Damien; Raynal, Michel (25 July 2010). <a rel="nofollow" class="external text" href="https://hal.inria.fr/inria-00454399/file/PI-1949.pdf">"The multiplicative power of consensus numbers"</a> (PDF). Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing. Association for Computing Machinery. pp. 26–35. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1835698.1835705">10.1145/1835698.1835705</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-60558-888-9</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:3179361">3179361</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20220127204746/https://hal.inria.fr/inria-00454399/file/PI-1949.pdf">Archived</a> (PDF) from the original on 27 January 2022. Retrieved 22 April 2021.</cite>

</li>

<li id="cite_note-41"><a href="#cite_ref-41">^</a> <cite id="CITEREFFichHendlerShavit2004" class="citation book cs1">Fich, Faith; Hendler, Danny; Shavit, Nir (25 July 2004). "On the inherent weakness of conditional synchronization primitives". Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing. Association for Computing Machinery. pp. 80–87. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.96.9340">10.1.1.96.9340</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1011767.1011780">10.1145/1011767.1011780</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>1-58113-802-4</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:9313205">9313205</a>.</cite>

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite id="CITEREFHerlihyShavit1999" class="citation journal cs1">Herlihy, M.; Shavit, N. (1999). "The topological structure of asynchronous computability". Journal of the ACM. 46 (6): 858. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.78.1455">10.1.1.78.1455</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F331524.331529">10.1145/331524.331529</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:5797174">5797174</a>.</cite></li>

<li><cite id="CITEREFSaksZaharoglou2000" class="citation journal cs1">Saks, M.; Zaharoglou, F. (2000). "Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge". <a href="SIAM_Journal_on_Computing" title="SIAM Journal on Computing">SIAM Journal on Computing</a>. 29 (5): 1449–1483. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2FS0097539796307698">10.1137/S0097539796307698</a>.</cite></li>

<li>Bashir, Imran. "Blockchain Consensus." Blockchain Consensus - An Introduction to Classical, Blockchain, and Quantum Consensus Protocols. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4842-8178-9</bdi> Apress, Berkeley, CA, 2022. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-1-4842-8179-6">10.1007/978-1-4842-8179-6</a></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-19" href="https://en.wikipedia.org/wiki/?title=Consensus_(computer_science)&oldid=1296427069">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>